package questionSolution.Question_121;
/*
该问题的核心是找到最佳的买入和卖出时机，使得卖出价与买入价的插值最大（卖出必须在买入之后）。
最经典且高效的解法是一次遍历法（贪心思想），时间复杂度为O(n)，空间复杂度为O（0）
遍历数组时，维护两个变量：
minPrice:表示到当前天为止的最低买入价（确保买入在卖出之前）
maxPrice:表示当前能获取的最大利润
对于每一天的价格：
如果当前价格比minPrice更低，更新minPrice，找到更优的买入点
否则，计算当前价格卖出的利润（Prices[i] - minPrice）,并更新maxProfit
 */
public class Solution_1 {
    public int maxProfit(int[] prices) {
        int res = 0;
        int minPrice = prices[0];
        for (int i = 1; i < prices.length; i++){
            if (prices[i] < minPrice){
                minPrice = prices[i];
            }else{
                if(prices[i] - minPrice > res){
                    res = prices[i] - minPrice;
                }
            }
        }
        return res;
    }

    static void main() {
        Solution_1 sol = new Solution_1();
        System.out.println(sol.maxProfit(new int[]{1,2,3,4,5}));
    }
}
